package leetcode每日一题.leetcode20212;

import java.util.PriorityQueue;

/**
 * 1. 问题描述
 *      设计一个找到数据流中第k大元素的类（class）。注意是排序后的第k大元素，不是第k个不同的元素。
 *      请实现KthLargest类：
 *      KthLargest(int k, int[] nums)使用整数k和整数流nums初始化对象。
 *      int add(int val)将val插入数据流nums后，返回当前数据流中第k大的元素。
 *
 * 2. 算法分析
 *      首先我们第一反应是排序，然后直接返回第k大的元素即可，此时的时间复杂度为O(nlogn)(通过jdk底层封装的qs)
 *      如果数组的长度过大，时间复杂度还是比较高的。
 *      对于一个数组或者更为一般的集合，我们考虑集合的最值问题的是否，尤其是变化的最值或者局部的最值，我们通常
 *      会通过Heap或者PriorityQueue来优化，时间复杂度可以降低为O(1),当然此时我们并不考虑heap或者优先队列
 *      构建。
 *      注意一点：heap和PriorityQueue之间的关系，即PriorityQueue的底层通过heap来做的优化，所以两者基本
 *      上可以看成一个结构
 *
 *      下面分析题意：
 *         首先我们给定一个数组，每次插入新的元素进来之后我们需要找到当前数组的第k大的元素，注意数组是变化的
 *         分析具体的操作：add(int val)实现将val插入到数组中(本质不是数组，而是我们定义的heap或者优先队
 *         列，这一点题目的含义表示有点不是很明确，应该是翻译的问题)
 *         初始化时我们需要将给定的数组中的元素添加到对应的容器中，调用add方法实现即可，最后考虑add方法如何
 *         实现，根据heap的特点，让heap维护前k大的元素(此时使用小顶堆，root节点就是当前k最大元素)，即heap
 *         的size大于k，此时就需要poll出来(这一步就是维护的操作)
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q010_数据流中的第K大元素 {

    // 采用优先队列实现
    class KthLargest {

        PriorityQueue<Integer> heap; // 创建一个堆(本质是优先队列，用于维护局部k最大值)
        int k;

        public KthLargest(int k, int[] nums) {
            this.k = k;
            heap = new PriorityQueue<>();
            for(int x : nums) { // 将nums中所有的元素入堆
                add(x);
            }
        }

        public int add(int val) {
            heap.add(val);
            if(heap.size() > k) {
                heap.poll();
            }
            return heap.peek();
        }
    }
}
